home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1996 / MacHack 1996.toast / Presentations / Presentations ’94 / Timothy Knox / Help / Help Files / Miscellaneous / Unknown Values < prev   
Text File  |  1994-06-24  |  2KB  |  47 lines
  1. {••••• Programming with unknown values:Two examples… The 2nd is original •••••}
  2.  
  3. ;;; Problem: from the book "Functionnal programming"
  4. ;;; given an integer list l, built in one pass a list where each element
  5. ;;; is equal to the maximum element in l
  6.  
  7. ;;; A first solution with an UNKNOWN VALUE
  8. ;;; LOOK at it with attention… max is unknown and it works !
  9.  
  10. (define (rbm l)
  11.   (letrec [((f n rest&maxc)(cons (cons max (0 rest&maxc))
  12.                                  (cond (>? n (-1 rest&maxc)) n (-1 rest&maxc))))
  13.            (rest (reduce f '(() | 0) l))
  14.            (max (-1 rest))]
  15.           (0 rest)))
  16.  
  17. ;;; Another one, much more difficult to write in ONE PASS w/o lazyness
  18. ;;; and therefore Unknown Values
  19.  
  20. ;;; Problem: given a binary tree whose leaf are numbers, built a tree with
  21. ;;; the same structure, but whose leaves are the leaves of the first
  22. ;;; divided by the sum of all the leaves of the first tree in ONE PASS
  23.  
  24. (define leaf? number?)     ;Is it a leaf ?
  25. (define empty? null?)            ;Is it empty ?    
  26. (define left-son 0)        ;Access to left son
  27. (define right-son -1)      ;Access to right son
  28. (define values cons)                      ;To create pseudo multiple values
  29. (define processed 0)       ;To access first element of a Multiple Value
  30. (define sum -1)            ;To access 2nd element of a Multiple Value
  31.  
  32. (define (normalize tree)
  33.   (letrec [((norm+sum tree)
  34.               (cond (empty? tree) (values () 0)
  35.                     (leaf? tree)  (values (/ tree TotalSum) tree)
  36.                     (let [(left (norm+sum (left-son tree)))
  37.                           (right (norm+sum (right-son tree)))]
  38.                          (values (cons (processed left) (processed right))
  39.                                  (+ (sum left) (sum right))))))
  40.            (Both (norm+sum tree))
  41.            (ProcessedTree (processed Both))
  42.            (TotalSum (sum Both))]
  43.            ProcessedTree))
  44.  
  45. (normalize '(((0.|1.)|3.)|((6.|8.)|2.)))
  46. { = ((( 0.0e+0 | 5.0e-2) | 1.5e-1) ( 3.0e-1 | 4.0e-1) | 1.0e-1) }
  47.